package algorithm.dynamicProgramming.leetcode;
//1137. 第 N 个泰波那契数
public class tribonacci {
    public static void main(String[] args) {
        System.out.println(tribonacci2(25));
    }

    public static int tribonacci(int n) {
            if (n==0){
                return 0;
            }else if(n==1||n==2){
                return 1;
            }

            int[] f = new int[n+1];
            f[0]=0;
            f[1]=1;
            f[2]=1;
            for (int i=3;i<=n;i++){
                f[i] = f[i-3]+f[i-2]+f[i-1];
            }
            return f[n];
    }
    public static int tribonacci2(int n) {
        if (n==0){
            return 0;
        }else if(n==1||n==2){
            return 1;
        }

        int l=1,q=0,p=0,r=1;
        for (int i =3;i<=n;i++){
            p=q;
            q=l;
            l=r;
            r=p+q+l;
        }
        return r;
    }
}
